Новый алгоритм для вычисления индексов пересечения циклов 

Евгений Иванович Яковлев, доктор физико-математических наук, профессор, ведущий научный сотрудник Международной лаборатории динамических систем и приложений, профессор кафедры фундаментальной математики, Национальный исследовательский университет «Высшая школа экономики» (Россия, г. Нижний Новгород, ул. Б. Печерская, 25/12), eyakovlev@hse.ru

Актуальность и цели. Объекты исследования – триангулированные компактные полиэдры P, являющиеся n - мерными многообразиями с краем. Цель –создание новых эффективных алгоритмов для вычисления индексов пересечения по модулю 2. Материалы и методы. Используется построение замкнутого n - мерного пути вдоль заданного абсолютного одномерного цикла x . Результаты. Разработан алгоритм, позволяющий вычислить индекс пересечения заданного абсолютного одномерного цикла x с произвольным относительным циклом размерности (n - 1). Дано строгое математическое обоснование алгоритма. Выводы. Для рассматриваемой задачи алгоритм решения разработан впервые. Его вычислительная сложность равна O(n²N+m), где n – размерность многообразия P; N – количество его n -мерных симплексов; m – количество ребер, из которых состоит цикл x .

Ключевые слова

алгоритм, полиэдр, цикл, индекс пересечения

 Скачать статью в формате PDF

Для цитирования:

Яковлев Е. И. Новый алгоритм для вычисления индексов пересечения циклов // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. 2022. № 3. С. 3–10. doi:10.21685/2072-3040-2022-3-1